package hotLeetcode;

import java.util.Arrays;
import java.util.Map;

public class H15Leetcode53 {

    //暴力
    public int maxSubArray(int[] nums) {
//        Arrays.sort(nums);
        int result = Integer.MIN_VALUE;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                result = Math.max(result, sum);
            }

        }
        return result;
    }

    //思路二 : 滑动窗口
    public int maxSubArray2(int[] nums) {
        Arrays.sort(nums);
        //如果和在变大，就向右扩展
        int left = 0, right = nums.length;
        int sum = 0;
        while (right < nums.length) {
            int temp = 0;
            sum += temp;


        }

        return sum;
    }

    //贪心
    public int maxSubArray3(int[] nums) {
        int sum = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }

            if (sum > result) {
                result = sum;
            }


        }
        return result;



    }





    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        H15Leetcode53 h15Leetcode53 = new H15Leetcode53();
        System.out.println(h15Leetcode53.maxSubArray3(nums));
    }
}
